Energy-efficient optical acquisition schemes in wireless sensor networks

Energy-efficiency is an essential feature of wireless sensor networks (WSNs) where the longevity of autonomous sensor nodes is limited by their battery life and/or energy-harvesting capability. Base-station-initiated optical wireless communication with nodes equipped with a passive optical transmitter in the form of a corner cube retroreflector (CCR) provides sensor acquisition with no energy expenditure on the part of the sensor node itself and is therefore an attractive option for WSN. However, the return signal from an illuminated sensor node is a stochastic variable dependant on fabrication parameters, ambient conditions and receiver noise so that the sensor acquisition process is inherently error-prone. In this paper we propose an energy-aware, base station-initiated interrogation scheme based on exponentially increasing beam scan areas, that takes into consideration the error-prone trait of CCR-outfitted sensor nodes. We analyse the scheme performance subject to different values of signal variance and various cost functions. We extend the analysis to address the circumstance of a spatially-limited sensor-failure event, such as may be caused by deliberate tampering or by environmental factors. We show that agile beam-steering on the basis of accrued knowledge of contaminated sensor distributions promotes energy-conserving acquisition. The validity of a Poisson spatial distribution model for the sensor dispersion is discussed and the impact of this initial assumption on acquisition error is demonstrated.     

Self-stabilization of dynamic systems assuming only read/write atomicity

Summary Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion prootocol for tree structured systems. The second protocol is a spanning tree protocol for systems with any connected communication graph. The thrid protocol is obtianed by use offair protoco combination, a simple technique which enables the combination of two self-stabilizing dynamic protocols. The result protocol is a self-stabilizing, mutualexclusion protocol for dynamic systems with a general (connected) communication graph. The presented protocols improve upon previous protocols in two ways: First, it is assumed that the only atomic operations are either read or write to the shared memory. Second, our protocols work for any connected network and even for dynamic network, in which the topology of the network may change during the excution. Shlomi Dolev received his B.Sc. in Civil Engineering and B.A. in Computer Science in 1984 and 1985, and his M.Sc. and Ph.D. in computer Sciene in 1989 and 1992 from the Technion Israel Institute of Technology. He is currently a post-dotoral fellow in the Department of Computer Science at Texas A & M Univeristy. His current research interests include the theoretical aspects of distributed computing and communcation networks. Amos Israeli received his B.Sc. in Mathematics and Physics from Hebrew University in 1976, and his M.Sc. and D.Sc. in Computer Science from the Weizmann Institute in 1980 and the Technion in 1985, respectively. Currently he is a sensior lecturer at the Electrical Engineering Department at the Technion. Prior tot his he was a postdoctoral fellow at the Aiken Computation Laboratory at harvard. His research interests are in Parellel and Distributed Computing and in Robotics. In particular he has worked on the design and analysis of Wait-Free and Self-Stabilizing distributed protocols. Shlomo Moran received his B.Sc. and D.Sc. degrees in matheamtics from Technion, Israel Institute of Technology, Haifa, in 1975 and 1979, respectively. From 1979 to 1981 he was assistant professors and a visiting research specialist at the University of Minnesota, Minneapolis. From 1981 to 1985 he was a senior lecturer at the Department of Computer Science. Technion, and from 1985 to 1986 he visted at IBM Thoas J. Watson Research Center, Yorktown Heights. From 1986 to 1993 he was an associated professor at the Department of Computer Science, Technin. in 1992–3 he visited at AT & T Bell Labs at Murray Hill and at Centrum voor Wiskunde en Informatica, Amsterdam. From 1993 he is a full professor at the Department of Computer Science, Technion. His researchinterests include distributed algorithm, computational complexity, combinatorics and grapth theory.Part of this research was supported in part by Technion V.P.R. Funds — Wellner Research Fund, and by the Foundation for Research in Electronics, Computers and Communictions, administrated by the Israel Academy of Sciences and Humanities.     

Network of sensors: acquisition probability

A network of sensors is considered one of the most attractive remote sensing technologies available at present. In the system under consideration a network of sensors and a remote base station communicate using optical wireless links. This is accomplished by a base station that acquires and identifies sensors using a unique subcarrier frequency. The sensors use an active retroreflector to communicate with the base station, which reduces the complexity, cost, and power consumption of the sensors. The base station employs an imaging receiver (detector matrix), in which signals arriving from different directions are detected by different pixels. The imaging receiver mitigates ambient light noise and interference between simultaneous uplink transmissions from different sensors, provided that the transmissions are imaged onto disjoint sets of pixels. We describe a scheme that allows simultaneous acquisition and identification of a sensor in a network by an imaging receiver. A probability model of erroneous acquisition of this scheme due to noise is derived. The model's results indicate that the matrix size, the signal, and the noise powers have the greatest influence in determining acquisition probability.     

Incremental deployment of network monitors based on Group Betweenness Centrality

In many applications we are required to increase the deployment of a distributed monitoring system on an evolving network. In this paper we present a new method for finding candidate locations for additional deployment in the network. This method is based on the Group Betweenness Centrality (GBC) measure that is used to estimate the influence of a group of nodes over the information flow in the network. The new method assists in finding the location of k additional monitors in the evolving network, such that the portion of additional traffic covered is at least (1−1/e) of the optimal.     

Stabilizing data-link over non-FIFO channels with optimal fault-resilience

Self-stabilizing systems have the ability to converge to a correct behavior when started in any configuration. Most of the work done so far in the self-stabilization area assumed either communication via shared memory or via FIFO channels.This paper is the first to lay the bases for the design of self-stabilizing message passing algorithms over unreliable non-FIFO channels. We propose an optimal stabilizing data-link layer that emulates a reliable FIFO communication channel over unreliable capacity bounded non-FIFO channels (the channel capacity is known to the protocol).     

An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes

The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c₁,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c₁,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large.     

Geographic Quorum System Approximations

Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in the plane (representing servers) into quorums (i.e., clusters) of size k. The distance between a point p and a cluster C is the Euclidean distance between p and the site in C that is the farthest from p. We present a near linear time constant-factor approximation algorithm for partitioning X into clusters, such that the maximal distance between a point in the underlying region and its closest cluster is minimized. Next, we describe a data structure for answering (approximately) nearest-neighbor queries on such a clustering. Finally, we study the problem of partitioning into clusters with an additional load-balancing requirement.